home *** CD-ROM | disk | FTP | other *** search
/ Amiga Packmags / Source, The - Issue 5 (1993)(Epsilon)[WB].zip / Source, The - Issue 5 (1993)(Epsilon)[WB].adf / Source / Vectors / Rendering / Triangle.lha / polygon2triangles.code next >
Internet Message Format  |  1989-10-24  |  8KB
  1. From steinmetz!uunet!leah.Albany.EDU!rsb584 Tue Jan 26 21:46:45 1988
  2. Received:  by kbsvax.steinmetz (1.2/1.1x Steinmetz)
  3.      id AA02347; Tue, 26 Jan 88 12:14:57 est
  4. Received: from LEAH.ALBANY.EDU by uunet.UU.NET (5.54/1.14) 
  5.     id AA00664; Tue, 26 Jan 88 10:06:27 EST
  6. Date: Tue, 26 Jan 88 09:52:25 EST
  7. From: steinmetz!uunet!leah.Albany.EDU!rsb584 (Raymond S Brand)
  8. Received: by leah.Albany.EDU (5.58/1.1)
  9.     id AA12298; Tue, 26 Jan 88 09:52:25 EST
  10. Message-Id: <8801261452.AA12298@leah.Albany.EDU>
  11. To: beowulf!rsbx
  12.  
  13. >From nelson@esunix.UUCP Mon Jan 11 12:48:46 1988
  14. Path: leah!uwmcsd1!bbn!rochester!ur-tut!sunybcs!rutgers!im4u!ut-sally!utah-cs!utah-gr!uplherc!esunix!nelson
  15. From: nelson@esunix.UUCP (Scott Nelson)
  16. Newsgroups: comp.graphics
  17. Subject: Code: Polygon to triangle converter.
  18. Message-ID: <633@esunix.UUCP>
  19. Date: 11 Jan 88 17:48:46 GMT
  20. Distribution: na
  21. Organization: Evans & Sutherland, Salt Lake City, Utah
  22. Lines: 284
  23.  
  24. /*
  25.  * poly_tri.c
  26.  *
  27.  * Program to take a polygon definition and convert it into triangles
  28.  * that may then be rendered by the standard triangle rendering
  29.  * algorithms.  This assumes all transformations have been performed
  30.  * already and cuts them up into optimal triangles based on their
  31.  * screen-space representation.
  32.  *
  33.  *    Copyright (c) 1988, Evans & Sutherland Computer Corporation
  34.  *
  35.  * Permission to use all or part of this program without fee is
  36.  * granted provided that it is not used or distributed for direct
  37.  * commercial gain, the above copyright notice appears, and
  38.  * notice is given that use is by permission of Evans & Sutherland
  39.  * Computer Corporation.
  40.  *
  41.  *    Written by Reid Judd and Scott R. Nelson at
  42.  *    Evans & Sutherland Computer Corporation (January, 1988)
  43.  *
  44.  * To use this program, either write your own "draw_triangle" routine
  45.  * that can draw triangles from the definitions below, or modify the
  46.  * code to call your own triangle or polygon rendering code.  Call
  47.  * "draw_poly" from your main program.
  48.  */
  49.  
  50. #include <stdio.h>
  51.  
  52.  
  53. /* A single vertex */
  54.  
  55. typedef struct {
  56.     int color;        /* RGB */
  57.     float x;
  58.     float y;
  59.     float z;
  60. } vertex;
  61.  
  62.  
  63. /* A triangle made up of three vertices */
  64.  
  65. typedef vertex triangle[3];
  66.  
  67.  
  68. #define V_MAX 100    /* Maximum number of vertices allowed (arbitrary) */
  69.  
  70. #define BIG 1.0e30    /* A number bigger than we expect to find here */
  71.  
  72. #define COUNTER_CLOCKWISE 0
  73. #define CLOCKWISE 1
  74.  
  75.  
  76.  
  77. /*
  78.  * orientation
  79.  *
  80.  * Return either clockwise or counter_clockwise for the orientation
  81.  * of the polygon.
  82.  */
  83.  
  84. int orientation( n, v )
  85.     int n;            /* Number of vertices */
  86.     vertex v[];            /* The vertex list */
  87. {
  88.     float area;
  89.     int i;
  90.  
  91.     /* Do the wrap-around first */
  92.     area = v[n-1].x * v[0].y - v[0].x * v[n-1].y;
  93.  
  94.     /* Compute the area (times 2) of the polygon */
  95.     for (i = 0; i < n-1; i++)
  96.     area += v[i].x * v[i+1].y - v[i+1].x * v[i].y;
  97.  
  98.     if (area >= 0.0)
  99.     return COUNTER_CLOCKWISE;
  100.     else
  101.     return CLOCKWISE;
  102. } /* End of orientation */
  103.  
  104.  
  105.  
  106. /*
  107.  * determinant
  108.  *
  109.  * Computes the determinant of the three points.
  110.  * Returns whether the triangle is clockwise or counter-clockwise.
  111.  */
  112.  
  113. int determinant( p1, p2, p3, v )
  114.     int p1, p2, p3;        /* The vertices to consider */
  115.     vertex v[];            /* The vertex list */
  116. {
  117.     float x1, x2, x3, y1, y2, y3;
  118.     float determ;
  119.  
  120.     x1 = v[p1].x;
  121.     y1 = v[p1].y;
  122.     x2 = v[p2].x;
  123.     y2 = v[p2].y;
  124.     x3 = v[p3].x;
  125.     y3 = v[p3].y;
  126.  
  127.     determ = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
  128.     if (determ >= 0.0)
  129.     return COUNTER_CLOCKWISE;
  130.     else
  131.     return CLOCKWISE;
  132. } /* End of determinant */
  133.  
  134.  
  135.  
  136. /*
  137.  * distance2
  138.  *
  139.  * Returns the square of the distance between the two points
  140.  */
  141.  
  142. float distance2( x1, y1, x2, y2 )
  143.     float x1, y1, x2, y2;
  144. {
  145.     float xd, yd;        /* The distances in X and Y */
  146.     float dist2;        /* The square of the actual distance */
  147.  
  148.     xd = x1 - x2;
  149.     yd = y1 - y2;
  150.     dist2 = xd * xd + yd * yd;
  151.  
  152.     return dist2;
  153. } /* End of distance2 */
  154.  
  155.  
  156.  
  157. /*
  158.  * no_interior
  159.  *
  160.  * Returns 1 if no other point in the vertex list is inside
  161.  * the triangle specified by the three points.  Returns
  162.  * 0 otherwise.
  163.  */
  164.  
  165. int no_interior( p1, p2, p3, v, vp, n, poly_or )
  166.     int p1, p2, p3;        /* The vertices to consider */
  167.     vertex v[];            /* The vertex list */
  168.     int vp[];            /* The vertex pointers (which are left) */
  169.     int n;            /* Number of vertices */
  170.     int poly_or;        /* Polygon orientation */
  171. {
  172.     int i;            /* Iterative counter */
  173.     int p;            /* The test point */
  174.  
  175.     for (i = 0; i < n; i++) {
  176.     p = vp[i];        /* The point to test */
  177.     if ((p == p1) || (p == p2) || (p == p3))
  178.         continue;        /* Don't bother checking against yourself */
  179.     if (   (determinant( p2, p1, p, v ) == poly_or)
  180.         || (determinant( p1, p3, p, v ) == poly_or)
  181.         || (determinant( p3, p2, p, v ) == poly_or) ) {
  182.         continue;        /* This point is outside */
  183.     } else {
  184.         return 0;        /* The point is inside */
  185.     }
  186.     }
  187.     return 1;            /* No points inside this triangle */
  188. } /* End of no_interior */
  189.  
  190.  
  191.  
  192. /*
  193.  * draw_poly
  194.  *
  195.  * Call this procedure with a polygon, this divides it into triangles
  196.  * and calls the triangle routine once for each triangle.
  197.  *
  198.  * Note that this does not work for polygons with holes or self
  199.  * penetrations.
  200.  */
  201.  
  202. draw_poly( n, v )
  203.     int n;            /* Number of vertices in triangle */
  204.     vertex v[];            /* The vertex list (implicit closure) */
  205. {
  206.     int prev, cur, next;    /* Three points currently being considered */
  207.     int vp[V_MAX];        /* Pointers to vertices still left */
  208.     int count;            /* How many vertices left */
  209.     int min_vert;        /* Vertex with minimum distance */
  210.     int i;            /* Iterative counter */
  211.     float dist;            /* Distance across this one */
  212.     float min_dist;        /* Minimum distance so far */
  213.     int poly_orientation;    /* Polygon orientation */
  214.     triangle t;            /* Triangle structure */
  215.  
  216.     if (n > V_MAX) {
  217.     fprintf( stderr, "Error, more than %d vertices.\n", V_MAX);
  218.     return;
  219.     }
  220.  
  221.     poly_orientation = orientation( n, v );
  222.  
  223.     for (i = 0; i < n; i++)
  224.     vp[i] = i;        /* Put vertices in order to begin */
  225.  
  226. /* Slice off clean triangles until nothing remains */
  227.  
  228.     count = n;
  229.     while (count > 3) {
  230.     min_dist = BIG;        /* A real big number */
  231.     min_vert = 0;        /* Just in case we don't find one... */
  232.     for (cur = 0; cur < count; cur++) {
  233.         prev = cur - 1;
  234.         next = cur + 1;
  235.         if (cur == 0)    /* Wrap around on the ends */
  236.         prev = count - 1;
  237.         else if (cur == count)
  238.         next = 0;
  239.         /* Pick out shortest distance that forms a good triangle */
  240.         if (   (determinant( vp[prev], vp[cur], vp[next], v ) == poly_orientation)
  241.             /* Same orientation as polygon */
  242.         && no_interior( vp[prev], vp[cur], vp[next], v, vp, count, poly_orientation )
  243.             /* No points inside */
  244.         && ((dist = distance2( v[vp[prev]].x, v[vp[prev]].y,
  245.                        v[vp[next]].x, v[vp[next]].y )) < min_dist) )
  246.             /* Better than any so far */
  247.         {
  248.         min_dist = dist;
  249.         min_vert = cur;
  250.         }
  251.     } /* End of for each vertex (cur) */
  252.  
  253.     /* The following error should "never happen". */
  254.     if (min_dist == BIG)
  255.         fprintf( stderr, "Error: Didn't find a triangle.\n" );
  256.  
  257.     prev = min_vert - 1;
  258.     next = min_vert + 1;
  259.     if (min_vert == 0)    /* Wrap around on the ends */
  260.         prev = count - 1;
  261.     else if (min_vert == count)
  262.         next = 0;
  263.  
  264. /* Output this triangle */
  265.  
  266.     t[0].x = v[vp[prev]].x;
  267.     t[0].y = v[vp[prev]].y;
  268.     t[0].z = v[vp[prev]].z;
  269.     t[0].color = v[vp[prev]].color;
  270.     t[1].x = v[vp[min_vert]].x;
  271.     t[1].y = v[vp[min_vert]].y;
  272.     t[1].z = v[vp[min_vert]].z;
  273.     t[1].color = v[vp[min_vert]].color;
  274.     t[2].x = v[vp[next]].x;
  275.     t[2].y = v[vp[next]].y;
  276.     t[2].z = v[vp[next]].z;
  277.     t[2].color = v[vp[next]].color;
  278.  
  279.     draw_triangle( t );
  280.  
  281. /* Remove the triangle from the polygon */
  282.  
  283.     count -= 1;
  284.     for (i = min_vert; i < count; i++)
  285.         vp[i] = vp[i+1];
  286.     }
  287.  
  288. /* Output the final triangle */
  289.  
  290.     t[0].x = v[vp[0]].x;
  291.     t[0].y = v[vp[0]].y;
  292.     t[0].z = v[vp[0]].z;
  293.     t[0].color = v[vp[0]].color;
  294.     t[1].x = v[vp[1]].x;
  295.     t[1].y = v[vp[1]].y;
  296.     t[1].z = v[vp[1]].z;
  297.     t[1].color = v[vp[1]].color;
  298.     t[2].x = v[vp[2]].x;
  299.     t[2].y = v[vp[2]].y;
  300.     t[2].z = v[vp[2]].z;
  301.     t[2].color = v[vp[2]].color;
  302.  
  303.     draw_triangle( t );
  304.  
  305. } /* End of draw_poly */
  306.  
  307. /* End of poly_tri.c */
  308.  
  309.  
  310.